\section{Efficient Fanout Heuristics}\label{sec:heuristics}

\subsection{Intuition}

\subsection{Heuristic Results}

\begin{table}
  \caption{The heuristics for choosing $d$.}
  \label{tab:heuristicsresults}
  \begin{tabular}{l|c|c|c}
  \multicolumn{1}{r|}{$g^{c}\left( x \right) \rightarrow $} & sublinear & linear & superlinear\\
  $g^{s}\left(d\ g^{s}\left( x\right) \right) \downarrow $ & & & \\ \hline
  $< g^{s}\left( x\right) $ & & 2 & 2 \\ \hline
  $= g^{s}\left( x\right) $ & & $e$ & minimal (2 or $e$?) \\ \hline
  $> g^{s}\left( x\right) $ & $n$ & $n$ & \\ \hline
  \end{tabular}
\end{table}

%combine this with the previous table
\begin{table}
  \caption{Common distributed problems}
  \label{tab:commonproblems}
  \begin{tabular}{l|c|c|c}
  \multicolumn{1}{r|}{$g^{c}\left( x \right) \rightarrow $} & sublinear & linear & superlinear\\
  $g^{s}\left(d\ g^{s}\left( x\right) \right) \downarrow $ & & & \\ \hline
  $< g^{s}\left( x\right) $ & & &  \\ \hline
  $= g^{s}\left( x\right) $ & top-k match & &  \\ \hline
  $> g^{s}\left( x\right) $ & grep & word count,sort & some matrix operations\\ \hline
  \end{tabular}
\end{table}

\subsection{Selected Proofs}

\subsubsection{$g^{s}\left(d\ g^{s}\left( x\right) \right) = g^{s}\left( x\right) $ and linear $g^{c}\left( x \right) $}
\begin{enumerate}
  \item The total cost for a structure with size $d$ is $\sum_{x=1}^{\log _{d}n}cost_{communication} + cost_{aggregation}$
  \item The cost of communication is linear with respect to the size of the input. Since the output size at each level is the size of one of the inputs at the previous level, this is simply $d g^{s}\left( x_{0}\right) $ at every level times some constant $c_{comm}$, which essentially becomes a constant.
  \item The cost of aggregation can be similarly simplified to $g^{c}\left( x_{0}\right) $.
  \item $\sum_{x=1}^{\log _{d}n}c_{comm}d g^{s}\left( x_{0}\right) + g^{c}\left( x_{0}\right) $ = $c_{comm}d g^{s}\left( x_{0}\right)\sum_{x=1}^{\log _{d}n}1 + g^{c}\left( x_{0}\right)\sum_{x=1}^{\log _{d}n}1 $.
  \item $\therefore$ The total cost for fanout $d$ is $\left( \log _{d}n\right) \left( c_{comm}d g^{s}\left( x_{0}\right) + g^{c}\left( x_{0}\right)\right)$.
  \item $\log _{d}n$ expands to $\frac{\log n}{\log d}$, and $\log n$, $c_{comm}$, $g^{s}\left( x_{0}\right)$, and $g^{c}\left( x_{0}\right)$ are not configurable by the fanout. Thus the configurable portion of the equation in $\frac{d}{\log d}$, which is optimized at $d=e$.
\end{enumerate}
 
\subsubsection{$g^{s}\left(d\ g^{s}\left( x\right) \right) = g^{s}\left( x\right) $ and superlinear $g^{c}\left( x \right) $}
\begin{enumerate}
  \item Start by proving that a the linear $g^{c}\left( x \right) $ case becomes less optimal as $d$ grows.
  \item If the fanout is increased without decreasing the number of levels in the tree, then obviously the time will increase. Both communication and aggregation increase linearly by a factor of $\frac{d+1}{d}$, but there is no decrease in the number of levels summed. Thus, we repeat the analysis not for $d+1$, but for $d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}$, which is the lowest value for $d$ which will decrease the height of the tree.
  \item The communication time becomes $\sum_{x=1}^{\log _{d}n\ -\ 1}c_{comm} g^{s}\left( x\right) d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}$.
  \item Again replacing the $x$ in $g^{s}\left( x\right)$ with $x_{0}$ and treating it like a constant because it is the same at all levels, this simplifies to $c_{comm} g^{s}\left( x_{0}\right) d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}\sum_{x=1}^{\log _{d}n\ -\ 1}1$ = $c_{comm} g^{s}\left( x_{0}\right) d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1} \left( \log _{d} n\ -\ 1\right) $ = $g^{s}\left( x_{0}\right) d n^{\log _{d}} n$.
  \item Assuming $2 \leq d \leq n$, $n^{\log _{d} n} > \log _{d} n $, so the communication cost for the  $d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}$ ($g^{s}\left( x_{0}\right) d n^{\log _{d}} n$) is higher than for $d$ ($g^{s}\left( x_{0}\right) d \log _{d} n$).
  \item For the cost of aggregation, the comparison is between $\sum_{x=1}^{\log_{d}n} g^{c}\left( d\ g^{s}\left( x\right)\right)$ and $\sum_{x=1}^{\log _{d}n\ -\ 1}g^{c}\left( d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}g^{s}\left( x\right)\right)$.
  \item Assume that $g^{s}\left( x\right)$ can again be simplified. The equations now become $g^{c}\left( d\ g^{s}\left( x_{0}\right)\right)\left( \log_{d} n\right)$ and $g^{c}\left( d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}g^{s}\left( x_{0}\right)\right)\left(\log _{d}n\ -\ 1\right) $.
  \item In the case that $g^{c}\left(\right)$ is linear and goes through $0$, the value passed in is simply multiplied by a constant, further simplifying the equations to $c_{linear} d\ g^{s}\left( x_{0}\right)\left( \log_{d} n\right)$ and $c_{linear} d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}g^{s}\left( x_{0}\right)\left(\log _{d}n\ -\ 1\right)  = c_{linear} d n^{\log _{d} n}g^{s}\left( x_{0}\right) $. As with the communication analysis, recalling that $2 \leq d \leq n$, $n^{\log _{d} n} > \log _{d} n $ makes it clear that the cost for $d$ is less than that for $d\frac{n^{\log _{d} n}}{\log _{d} n\ -\ 1}$.
  \item In the case that $g^{c}\left(\right)$ is superlinear, the increase will be more substantial than in the case of linear $g^{c}\left(\right)$. Therefore, this analysis extends to the superlinear case.
  \item Since communication cost and aggregation cost both increase when the fanout is increased with $g^{s}\left(d\ g^{s}\left( x\right) \right) = g^{s}\left( x\right) $ and linear or superlinear $g^{c}\left( x \right) $, the conclusion is that minimal fanout ($d = 2$) is preferred. 
\end{enumerate}

\subsubsection{$g^{s}\left(d\ g^{s}\left( x\right) \right) > g^{s}\left( x\right) $ and linear or sublinear $g^{c}\left( x \right) $}
\begin{enumerate}
  \item Assume that at each level, the output grows proportionally with respect to the size of the output. Let's call this growth factor $y$ such that $g^{s}\left(d\ g^{s}\left( x\right) \right) = y \, g^{s}\left( x\right) $ for $y > 1$.
  \item Intuitively, with the growth factor each level will do more work than the previous level (although more levels means doing more in parallel at the lower levels), therefore let us consider the base case of a single level, which with linear communication and computation assumptions take time $\left( c_{comm} + c_{agg}\right) \, n \, g^s\left( x_{0}\right)$. 
    \item The total cost of the system in with the given assumptions can be represented by \\ $\sum _{x=1}^{\log_{d}n}\left( c_{comm} \left(d\, g^{s}\left( x_{0}\right)\frac{\prod _{z=1}^{x}}{y} \right) + c_{agg} \left(d\, g^{s}\left( x_{0}\right)\frac{\prod _{z=1}^{x}} {y} \right) \right)$ $=$ $d\, g^{s}\left( x_{0}\right) \left( c_{comm} + c_{agg}\right)\sum _{x=1}^{\log_{d}n}\frac{\prod _{z=1}^{x} y}{y} $ because the size of the input increases by a factor of $y$ for every level up the tree \emph{after the first}.
  \item The total cost representation of the system is thus reducible to $d\, g^{s}\left( x_{0}\right) \, \left( c_{comm} + c_{agg}\right) \frac{\left(y^{\log_{d}n} - 1 \right)}{y-1}$ under these conditions.
  \item To find the case when a single aggregation level is preferable, we solve for $d\, g^{s}\left( x_{0}\right) \, \left( c_{comm} + c_{agg}\right) \frac{\left(y^{\log_{d}n} - 1 \right)}{y-1} > \left( c_{comm} + c_{agg}\right) \, n \,g^s\left( x_{0}\right)$. We replace $d$ with $\sqrt[h]{n}$, and $y^{\log_{d}n}$ correspondingly becomes $y^{h}$.
  \item This simplifies the problem to $\sqrt[h]{n}\, \frac{\left(y^{h} - 1 \right)}{y-1} > n $, or $\frac{\left(y^{h} - 1 \right)}{y-1} > n^{1-\frac{1}{h}} $.
  \item $\frac{\left(y^{h} - 1 \right)}{y-1}$ $>$ $\frac{\left(y^{h} - y \right)}{y-1}$ $=$ $\frac{y\left(y^{h} - 1 \right)}{y-1}$ $>$ $y^{h} - 1$ $>$ $y^{h}$ $>$ $n^{1-\frac{1}{h}} $. Therefore the inequality holds when $y$ $>$ $n^{\left( 1-\frac{1}{x}\right)\left( \frac{1}{h}\right)}$ $=$ $n^{\frac{h-1}{h^{2}}}$.
  \item In the cases we consider, growth is more likely to be proportional to $d$ than $n$. Plugging $d$ into $n^{\frac{h-1}{h^{2}}}$ gives $\left( d^{h}\right)^{\frac{h-1}{h^{2}}}$ $=$ $d^{\frac{h-1}{h}}$ $=$ $d^{\frac{log_{d}n-1}{log_{d}n}}$ for $2 \leq d \leq n$.
  \item To find the extreme case, we find the derivative and set it to 0. $\frac{\partial}{\partial d} d^{\frac{log_{d}n-1}{log_{d}n}}$ $=$ $\frac{d^{-\log_{d}n}\left(\log\frac{n}{d^2}\right)}{\log n}$ $=$ $\frac{d^{-\log_{d}n}\left(\log n \, - \, 2\log{d}\right)}{\log n} = 0$. This is true when $\log n = 2\log{d}$, or $n=d^{2}$.
  \item The second derivative is $\frac{2 \, d^{\log_{n}d \, + \, 1}\left(\log d \, \log n - 2\log^{2}d + \log n\right)}{\log^{2}n}$, which is positive for $n=d^{2}$, $2 \leq 2 \leq n$, meaning that this is a maximum value. Plugging the maximum $n=d^{2}$ into the equation $d^{\frac{log_{d}n-1}{log_{d}n}}$ yields $d^{\frac{2-1}{2}}$, or $\sqrt[2]{d}$ Therefore, it is always better to have a single layer of aggregation as long as $y \geq \sqrt[2]{d}$.
  \item This analysis assumes the $g^{c}\left( x_0\right) + \ldots + g^{c}\left( x_z\right)$ $=$ $g^{c}\left( x_0 + \ldots + x_z\right)$. However, in the case that $g^{c}\left(\right)$ is sublinear, this no longer holds. In fact, the cost of multiple layers, with multiple applications of $g^{c}\left(\right)$ on smaller inputs, would be even higher relative to the cost of a single layer. Therefore this analysis holds for the sublinear $g^{c}\left(\right)$ case as well.
\end{enumerate}

In the case that $1 < y < \sqrt[2]{d} $, the ideal fanout is still not known. However, it is worth noting that the maximum occurs very close to the intuitive case of a single layer. Therefore, heuristically it makes sense to have relatively high fanout when the size of the output is known to measurably grow in proportion to the size of the input. When $y$ is known to be very small, it might make sense to choose a smaller $d$, but for the sake of simple heuristics, we simply use $d=n$.

\subsubsection{$g^{s}\left(d\ g^{s}\left( x\right) \right) < g^{s}\left( x\right) $ and linear and superlinear $g^{c}\left( x \right) $}
\begin{enumerate}
  \item Assume that at each level, the output grows proportionally with respect to the size of the output. Let's call this growth factor $y$ such that $g^{s}\left(d\ g^{s}\left( x\right) \right) = y \, g^{s}\left( x\right) $ for $y < 1$. 
    \item The total cost of the system in with the given assumptions can be represented by \\ $\sum _{x=1}^{\log_{d}n}\left( c_{comm} \left(d\, g^{s}\left( x_{0}\right)\frac{\prod _{z=1}^{x}}{y} \right) + c_{agg} \left(d\, g^{s}\left( x_{0}\right)\frac{\prod _{z=1}^{x}} {y} \right) \right)$ $=$ $d\, g^{s}\left( x_{0}\right) \left( c_{comm} + c_{agg}\right)\sum _{x=1}^{\log_{d}n}\frac{\prod _{z=1}^{x} y}{y} $ because the size of the input increases by a factor of $y$ for every level up the tree \emph{after the first}.
  \item The total cost representation of the system is thus reducible to $d\, g^{s}\left( x_{0}\right) \, \left( c_{comm} + c_{agg}\right) \frac{\left(y^{\log_{d}n} - 1 \right)}{y-1}$ under these conditions.
  \item $g^{s}\left( x_{0}\right)$, $c_{comm}$, and  $c_{agg}$ are given, so the goal is to find the minimum for  $d\, \frac{\left(y^{\log_{d}n} - 1 \right)}{y-1}$ for $2 \leq d \leq n$.
  \item We take the derivative to find any extreme values. $\frac{\partial}{\partial d} d^{\frac{log_{d}n-1}{log_{d}n}}$ $=$ $\frac{d^{-\log_{d}n}\left(\log\frac{n}{d^2}\right)}{\log n}$ $=$ $\frac{d^{-\log_{d}n}\left(\log n \, - \, 2\log{d}\right)}{\log n} = 0$. This is true when $\log n = 2\log{d}$, or $n=d^{2}$.
  \item The second derivative is $\frac{2 \, d^{\log_{n}d \, + \, 1}\left(\log d \, \log n - 2\log^{2}d + \log n\right)}{\log^{2}n}$, which is positive for $n=d^{2}$, $2 \leq 2 \leq n$, meaning that this is a maximum value. Thus the minimum value happens at one of the endpoints.
  \item $d\, \frac{\left(y^{\log_{d}n} - 1 \right)}{y-1}$ at 2 is $2\, \frac{\left(y^{\log_{2}n} - 1 \right)}{y-1}$, and at $n$ is $n\, \frac{\left(y^{\log_{n}n} - 1 \right)}{y-1}$ $=$ $n\, \frac{\left(y - 1 \right)}{y-1}$ $=$ $n$.
  \item Assuming $n>2$ and $y<1$, $y^{\log_{2}n}\, -\, 1\, <\, y\, -\, 1$, so $\frac{\left(y^{\log_{2}n} - 1 \right)}{y-1} < 1$, and $2\, \frac{\left(y^{\log_{2}n} - 1 \right)}{y-1}$ $<$ 2 $<$ $n$.
  \item $\therefore$ The optimal fanout is 2.
  \item This analysis assumes the $g^{c}\left( x_0\right) + \ldots + g^{c}\left( x_z\right)$ $=$ $g^{c}\left( x_0 + \ldots + x_z\right)$. However, in the case that $g^{c}\left( x_0\right)$ is superlinear, that does not hold. In fact, doing more computation at each level (both from higher fanout and fewer levels to decrease the input size) increases the computation cost even more, which further increases the improvements seen by creating a taller tree. Therefore this analysis holds for superlinear $g^{c}\left(\right)$ as well.
\end{enumerate}

%\begin{table}
%  \caption{The ideal fanout for $g^{s}\left(d\ g^{s}\left( x\right) \right) > g^{s}\left( x\right) $ and $g^{c}\left( x \right)$ is linear.}
%  \label{tab:growth}
%  \begin{tabular}{l|c|c|c}
%  \multicolumn{1}{r|}{$g^{c}\left( x \right) \rightarrow $} & sublinear & linear & superlinear\\
%  $g^{s}\left(d\ g^{s}\left( x\right) \right) \downarrow $ & & & \\ \hline
%  $< g^{s}\left( x\right) $ & & & \\ \hline
%  $= g^{s}\left( x\right) $ & & $d = e$ & \\ \hline
%  $> g^{s}\left( x\right) $ & & dependent on $y$ & \\ \hline
%  \end{tabular}
%\end{table}
